package com.example.demo.zaqizabatest.sort;

import java.util.Arrays;

/**
 * @ClassName QuickSort
 * @Author lys4134
 * @Date 2022/03/04 14:44:28
 * @Description QuickSort
 * @Version 1.0
 **/
public class QuickSort {

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 6, 9, 8, 10, 1};
        sort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 1、定一个key，再定一个左指针和右指针
     * 2、当nums[r]>=key,执行r--,迭代至nums[r]<key;当nums[l]<=key,执行l++,迭代至nums[l]<key;交换l和r的值（前提l<r）  步骤2需迭代
     * 3、当l==r交换l与key的位置，再将当前数组拆分为两个数组分别递归
     * @param nums
     * @param left 子数组左下标
     * @param right 子数组右下标
     */
    public static void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int l = left;
        int r = right;
        int key = nums[left];
        while (l < r) {
            while (nums[r] >= key && l < r) {
                r--;
            }
            while (nums[l] <= key && l < r) {
                l++;
            }
            swap(nums, l, r);
        }
        // 此时l==r一定为true
        swap(nums, left, l);
        sort(nums, left, l - 1);
        sort(nums, l + 1, right);

    }


    /**
     * 交换位置
     *
     * @param nums
     * @param i
     * @param j
     */
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}
